/***尚硅谷Java数据结构与java算法                    ***/
/***https://www.bilibili.com/video/BV1E4411H73v ***/
/***单向环形链表  解决约瑟夫问题     P27             ***/
/***C++ 实现版本    written by Daniel            ***/
/* chck 查看编码，默认是GBK2312 vs是utf-8  使用chck 65001 可设置为utf-8*/
#include <iostream>
#include <Windows.h>
using std::cout;
using std::endl;
#if 0
#define WIN_32
#endif
typedef struct node
{
    int num;
    node *next;
    node(int i) : num(i), next(nullptr) {}
    node(int i, node *newNode) : num(i), next(newNode) {}
} node;
//创建一个单向环形链表
//参数：num 输入环形链表的节点数量

//返回值：返回环形链表的头节点
class CircleList
{
public:
    //输入一个变量，创建一个 含有 num 个数据的环形链表
    CircleList() = delete;
    CircleList(int num)
    {
        if (num <= 0)
        {
            cout << "请输入一个大于0的数!" << endl;
            return;
        }
        node *curNode = nullptr;
        for (int i = 0; i < num; i++)
        { //创建一个新节点
            node *newNode = new node(i + 1);
            if (i == 0)
            {
                first = newNode;
                first->next = first;
                curNode = first;
                continue;
            }
            curNode->next = newNode;
            newNode->next = first;
            curNode = newNode;
        }
        size = num;
        return;
    }

    void print()
    {
        if (first == nullptr)
        {
            cout << "环形链表为空！\n"
                 << endl;
        }
        auto temp = first;
        do
        {
            cout << temp->num << "\t" << endl;
            temp = temp->next;
        } while (temp != first);
        return;
    }

    void getOne(int start, int inter, int size)
    {
        node *helper = first;
        if (start > size || inter < 1)
        {
            cout << "输入参数有误！" << endl;
        }
        //先将helper 指向第一个节点
        while (true)
        {
            if (helper->next == first)
            {
                break;
            }
            helper = helper->next;
        }
        //然后通过start参数，修改起始起点
        for (int i = 1; i < start; i++)
        {
            first = first->next;
            helper = helper->next;
        }
        while (first != nullptr)
        {
            for (int i = 1; i < inter; i++)
            {
                first = first->next;
                helper = helper->next;
            }
            node *nodeToDel = first;
            cout << nodeToDel->num << "号出队" << endl;
            first = first->next;
            helper->next = first;
            if (nodeToDel != nullptr)
            {
                delete nodeToDel;
                nodeToDel = nullptr;
            }
            if (first == helper)
            {
                cout << first->num << "号出队" << endl;

                delete (first);
                first = nullptr;
            }
        }
    }
    // 析构函数，回收整个链表，析构不成功！！！
    ~CircleList()
    {
        node *temp = first;
        node *nodeToDel = nullptr;
        while (size > 0)
        {
            nodeToDel = temp;
            temp = temp->next;
            if (nodeToDel != nullptr)
            {

                delete nodeToDel;
                if (nodeToDel == nullptr)
                {
                    cout << "nodeToDel是个空指针" << endl;
                }
                //防止编程nodeToDel变为野指针
                nodeToDel = nullptr;
                cout << "删除一个节点" << endl;
#ifdef WIN_32
                Sleep(1000);
#endif
            }
            size--;
        }
        cout << "环形链表回收成功" << endl;
    }

private:
    int size = 0;
    node *first = nullptr;
};

int main(int argc, char **argv)
{
    CircleList circle(120);
    circle.print();
    circle.getOne(10, 13, 120);
    return 0;
}
